package leetcode.editor.cn;

//给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。 
//
// 返回所有可能的结果。答案可以按 任意顺序 返回。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "()())()"
//输出：["(())()","()()()"]
// 
//
// 示例 2： 
//
// 
//输入：s = "(a)())()"
//输出：["(a())()","(a)()()"]
// 
//
// 示例 3： 
//
// 
//输入：s = ")("
//输出：[""]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 25 
// s 由小写英文字母以及括号 '(' 和 ')' 组成
// s 中至多含 20 个括号 
// 
// Related Topics 广度优先搜索 字符串 回溯 👍 760 👎 0

import java.util.*;

/**
 * Java：【301】- 删除无效的括号
 */
public class LeetCode_301_RemoveInvalidParentheses{
    public static void main(String[] args) {
        Solution solution = new LeetCode_301_RemoveInvalidParentheses().new Solution();
        // TO TEST
        List<String> strings = solution.removeInvalidParentheses("((()((s((((()");
        System.out.println(strings);
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        if(isValid(s)) {
            ArrayList<String> list = new ArrayList<>();
            list.add(s);
            return list;
        }
        Set<String> res = new HashSet<>(); // 结果去重
        Queue<String> queue = new LinkedList<>();
        queue.add(s);
        while (res.isEmpty()){
            int size = queue.size();
            Set<String> set =new HashSet<>(); // 子串去重
            for (int i = 0; i < size; i++) {
                String curr = queue.poll();
                int len = curr.length();
                for (int j = 0; j < len; j++) {
                    if(!(curr.charAt(j) == '(' || curr.charAt(j)==')'))
                        continue;
                    String tmp = curr.substring(0,j) + curr.substring(j+1,len); // 去除单个字符
                    if(isValid(tmp)){
                        res.add(tmp);
                    }else{
                        set.add(tmp);
                    }
                }
            }
            queue.addAll(set);
        }
        return new ArrayList<>(res);
    }

    public boolean isValid(String s){
        char[] chars = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        for (char ch : chars) {
            if (ch == '(') stack.push(ch);
            if (ch == ')') {
                if (stack.isEmpty() || stack.peek()!='(')
                    return false;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}